/*
题目：三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
https://leetcode.cn/problems/triangle/description/
 */
public class ＭinimumTotal {
    // 动态规划 + 滚动数组
    public int minimumTotal(List<List<Integer>> triangle) {
        int r = triangle.size();
        int src = Integer.MAX_VALUE;

        // 滚动数组逻辑上有点问题：使用两个一维数组交替使用
        int[] last = new int[r];
        int[] cur = new int[r];
        last[0] = triangle.get(0).get(0);

        for (int i = 1; i < r; i ++) {
            List<Integer> level = triangle.get(i);

            // 特殊处理一下 j = 0
            cur[0] = last[0] + level.get(0);

            for (int j = 1; j < i; j ++) {
                int value = level.get(j);
                cur[j] = Math.min(last[j], last[j - 1]) + value;

                if (i == r - 1) {  // 如果到了最后一行，就统计一下最小路径和
                    src = Math.min(src, cur[j]);
                }
            }

            // 再特殊处理一下最后一列，它只能是 上一行的最后一列 得到的
            cur[i] = last[i - 1] + level.get(i);

            int[] temp = last;
            last = cur;
            cur = temp; // 交换引用
        }
        src = Math.min(src, last[0]);
        return Math.min(src, last[r - 1]);
    }

    // 原始动归
    public int minimumTotall(List<List<Integer>> triangle) {
        // 动态规划，时间复杂度 O(n^2)  空间复杂度 O(n ^ 2)
        int r = triangle.size();
        int src = Integer.MAX_VALUE;

        int[][] dp = new int[r][r];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < r; i ++) {
            List<Integer> level = triangle.get(i);

            // 特殊处理一下 j = 0
            dp[i][0] = dp[i - 1][0] + level.get(0);

            for (int j = 1; j < i; j ++) {
                int value = level.get(j);
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + value;

                if (i == r - 1) {  // 如果到了最后一行，就统计一下最小路径和
                    src = Math.min(src, dp[i][j]);
                }
            }

            // 再特殊处理一下最后一列，它只能是 上一行的最后一列 得到的
            dp[i][i] = dp[i - 1][i - 1] + level.get(i);
        }
        src = Math.min(src, dp[r - 1][0]);
        return Math.min(src, dp[r - 1][r - 1]);
    }
}
